import java.util.Stack;

public class Leet20 {
    public static void main(String[] args) {

    }
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (!stack.empty()&&check(stack.peek(),s.charAt(i))){
                stack.pop();
            }else stack.push(s.charAt(i));
        }
        return stack.empty();
    }
    public boolean check(char a,char b){
        if (a=='('&&b==')')
            return true;
        else if (a=='{'&&b=='}')
            return true;
        else return a == '[' && b == ']';
    }
}
